package offer2

/**
原题链接:
https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

B站 Mysteryven
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。
对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
*/

var nodeList []*TreeNode

func Convert(pRootOfTree *TreeNode) *TreeNode {

	if pRootOfTree == nil { // 如果二叉搜索树是一棵空树直接返回空
		return nil
	}

	nodeList = []*TreeNode{}
	inOrder(pRootOfTree) // 调用遍历二叉树函数

	var head *TreeNode // 选择 nodeList 的第一个结点作为双向链表的头结点
	head = nodeList[0]
	head.Left = nil // 将头结点的上一个结点置为空
	preNode := head // 定义变量 preNode 用于指向当前被遍历节点的上一个结点,初始化的时候指向头结点

	for i := 1; i < len(nodeList); i++ { // 遍历 nodeList
		preNode.Right = nodeList[i] // 将 preNode 的后继结点指向当前被遍历的结点
		nodeList[i].Left = preNode  // 将当前被遍历结点的上一个结点指向 preNode
		preNode = preNode.Right     // preNode 向右移动
	}

	return head // 返回双向链表
}

func inOrder(curNode *TreeNode) { // 定义递归函数中序遍历二叉搜索树，并将遍历的结果加入到一个序列中
	if curNode == nil { // 递归结束的条件:当前被遍历的结点为空
		return
	}

	inOrder(curNode.Left)                // 递归处理当前结点的左子树
	nodeList = append(nodeList, curNode) // 处理中结点
	inOrder(curNode.Right)               // 递归处理当前结点的右子树
}
